package unionfindset;

import java.util.Arrays;

public class UnionFindSet2 {
    public int[] elem;

    //初始化
    public UnionFindSet2(int n) {
        elem = new int[n];
        Arrays.fill(elem, -1);
    }

    //查找元素属于哪个集合  x 下标
    public int findRoot(int x) {
        if(x < 0 || x >= elem.length) {
            throw new IndexOutOfBoundsException("下标范围不合法");
        }
        while(elem[x] >= 0) {
            x = elem[x];
        }
        return x;
    }

    //查看两个元素是否属于同一个集合
    public boolean isSameSet(int x1, int x2) {
        if(findRoot(x1) == findRoot(x2))
            return true;

        return false;
    }

    //将两个集合合并成一个集合
    public void union(int x1, int x2) {
        if(isSameSet(x1,x2)) {
            return;
        }
        int r1 = findRoot(x1);
        int r2 = findRoot(x2);
        elem[r1] += elem[r2];
        elem[r2] = r1;
    }

    //集合个数
    public int setSizes() {
        int count = 0;
        for(int x : elem) {
            if(x < 0) {
                count++;
            }
        }
        return count;
    }

/*    public static void main(String[] args) {
        UnionFindSet2 unionFindSet = new UnionFindSet2(10);
        unionFindSet.union(0,6);
        unionFindSet.union(6,7);
        unionFindSet.union(7,8);
        unionFindSet.union(1,4);
        unionFindSet.union(4,9);
        unionFindSet.union(2,3);
        unionFindSet.union(3,5);
        unionFindSet.union(6,7);
        System.out.println(Arrays.toString(unionFindSet.elem));
        unionFindSet.union(0,1);
        System.out.println(Arrays.toString(unionFindSet.elem));
    }

    public static void main1(String[] args) {
        UnionFindSet unionFindSet = new UnionFindSet(10);
        unionFindSet.elem = new int[]{-4,-3,-3,2,1,2,0,0,0,1};
        unionFindSet.union(0,1);
        System.out.println(Arrays.toString(unionFindSet.elem));

    }*/
}
